package com.suanfa.linkedlist;

import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.IntStream;

public class DynamicArray implements Iterable<Integer>{
    private int capacity =8;
    private int size=0;//逻辑大小
    private int[] array = new int[capacity];//静态数组

    public void addLast(int element){
        add(size,element);
    }
    /*
    * 头部和中部插入都需要拷贝数组，所以时间复杂度是O（n）
    * 尾部插入时间复杂度是O（1）
    * */

    public void add(int index, int element){
        checkAndGrow();
        if(index>=0 && index<size){
        System.arraycopy(array,index,array,index+1,size-index); //可以实现数组内，数组间的拷贝
        }
        array[index] = element;
        size++;
    }

    private void checkAndGrow() {
        if(size == 0){
            array = new int[capacity];
        }
        //容量检查
        else if(size == capacity){
            //进行扩容,1.5倍，java实现
            capacity += capacity >>1;
            int[] newArray = new int[capacity];
            System.arraycopy(array,0,newArray,0,size);
            array = newArray;
        }
    }

    public int get(int index){
        return array[index];
    }
    //遍历实现1
    public void foreach(Consumer<Integer> consumer){
        for(int i = 0;i<size;i++) {
            consumer.accept(array[i]);
            //函数式接口，有参数，无返回值，使用consumer
        }
    }
    //遍历实现2
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int i = 0;
            @Override
            public boolean hasNext() {
                return i<size;
            }

            @Override
            public Integer next() {
                return array[i++];
            }


        };
    }
    //遍历实现3
    public IntStream stream(){
        return IntStream.of(Arrays.copyOfRange(array,0,size));
    }


    //O(1)按索引  O(N)按值，只能遍历
    public int remove(int index){
        int removed = array[index];
        if(index<size-1){
            System.arraycopy(array,index+1,array,index,size-index-1);
        }
        size--;
        return removed;
    }
}
